package QuestionDaily;

public class minPathCost_2304 {
    /**
     * 细则详见leecode
     * @param grid 下标从 0 开始的整数矩阵 grid ，矩阵大小为 m x n ，由从 0 到 m * n - 1 的不同整数组成
     * @param moveCost moveCost[i][j] 是从值为 i 的单元格移动到下一行第 j 列单元格的代价。
     * @return 从 第一行 任意单元格出发，返回到达 最后一行 任意单元格的最小路径代价。
     */
    public int minPathCost(int[][] grid, int[][] moveCost) {
        /**
         * 思路动态规划
         * 用一个数组表示实时最小路径代价
         * 从每一行中选择路径加数值最小的节点
         */
        int high= grid.length,width=grid[0].length;
        int [][]pathCost=new int[high][width];
        //进行初始化
        for(int i=0;i<width;i++){
            pathCost[0][i]=grid[0][i];
        }
        for(int i=1;i<high;i++){  //从第二行开始处理
            for(int t=0;t<width;t++){  //列处理
                int minCost=pathCost[i-1][0]+moveCost[grid[i-1][0]][t];  //i -1 行层第一个数字到达 i 行 第 t 个数字的总代价
                for(int j=1;j<width;j++){  //找到上一层中到达第t个数字的最小代价
                    if(pathCost[i-1][j]+moveCost[grid[i-1][j]][t]<minCost){
                        minCost=pathCost[i-1][j]+moveCost[grid[i-1][j]][t];
                    }
                }
                pathCost[i][t]=minCost+grid[i][t];
            }
        }
        //找出最后一行最小的总代价
        int minCost=pathCost[high-1][0];
        for(int t=1;t<width;t++) {
            minCost=Integer.min(minCost,pathCost[high-1][t]);
        }
        return minCost;
    }
}
